// 版权所有2021 Go作者。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package modload

import (
	"cmd/go/internal/mvs"
	"context"
	"reflect"
	"sort"

	"golang.org/x/mod/module"
	"golang.org/x/mod/semver"
)

// editRequirements返回rs的编辑版本，以便：
// None
// 1.已选择mustSelect中的每个模块版本。
// None
// 2.tryUpgrade中的每个模块版本都升级到指定的版本
// 在不违反（1）的情况下，尽可能地修改版本。
// None
// 3.rs.rootModules中的每个模块版本（或rs.graph，如果rs.depth是渴望的）
// 仅在需要的范围内从其原始版本降级
// 满足（1），或仅升级到满足（1）和
// (2).
// None
// 4.没有任何模块升级到其路径的最大版本以上
// rs的依赖关系图，中版本的组合依赖关系图
// mustSelect，或中每个单独模块版本的依赖项
// tryUpgrade。
// None
// 通常，mustSelect中的模块版本是由于模块或
// 模块内的包将显式命令行参数与“go”匹配
// get'和tryUpgrade中的版本是可传递的依赖项
// 要么通过“go get-u”升级，要么通过添加来满足某些需求
// 否则将丢失包导入。
func editRequirements(ctx context.Context, rs *Requirements, tryUpgrade, mustSelect []module.Version) (edited *Requirements, changed bool, err error) {
	limiter, err := limiterForEdit(ctx, rs, tryUpgrade, mustSelect)
	if err != nil {
		return rs, false, err
	}

	var conflicts []Conflict
	for _, m := range mustSelect {
		conflict, err := limiter.Select(m)
		if err != nil {
			return rs, false, err
		}
		if conflict.Path != "" {
			conflicts = append(conflicts, Conflict{
				Source: m,
				Dep:    conflict,
				Constraint: module.Version{
					Path:    conflict.Path,
					Version: limiter.max[conflict.Path],
				},
			})
		}
	}
	if len(conflicts) > 0 {
		return rs, false, &ConstraintError{Conflicts: conflicts}
	}

	mods, changed, err := selectPotentiallyImportedModules(ctx, limiter, rs, tryUpgrade)
	if err != nil {
		return rs, false, err
	}

	var roots []module.Version
	if rs.depth == eager {
		// 在渴望模块中，提供由主服务器导入的包的模块
		// 模块可以是显式根或隐式传递依赖项。
		// 我们将mustSelect中的模块提升为明确的需求。
		var rootPaths []string
		for _, m := range mustSelect {
			if m.Version != "none" && m.Path != Target.Path {
				rootPaths = append(rootPaths, m.Path)
			}
		}
		if !changed && len(rootPaths) == 0 {
			// 构建列表没有更改，我们也没有要添加的新根。
			// 我们不需要重新计算模块的最小根。
			return rs, false, nil
		}

		for _, m := range mods {
			if v, ok := rs.rootSelected(m.Path); ok && (v == m.Version || rs.direct[m.Path]) {
				// m、 路径以前是根目录，其版本未更改或
				// 我们认为，它提供了一个由一个包直接导入的包
				// 或在主模块中进行测试。现在我们假设它仍然是
				// 相关的足以保持根。如果我们真的加载了所有的
				// 主模块中的包和测试（我们这里不做），
				// 我们可以在这一点上修改显式根。
				rootPaths = append(rootPaths, m.Path)
			}
		}

		roots, err = mvs.Req(Target, rootPaths, &mvsReqs{roots: mods})
		if err != nil {
			return nil, false, err
		}
	} else {
		// 在惰性模块中，提供由
		// 主模块必须保留为根模块。
		roots = mods
		if !changed {
			// 因为我们刚才计算的根是不变的，所以整个图必须
			// 和以前一样。保存原始rs，因为我们有
			// 可能已经加载了它的需求图。
			return rs, false, nil
		}
	}

	// 甚至不在生成列表中的模块必然无法提供
	// 任何进口的包裹。仅将以下直接模块标记为直接模块：
	// 仍在生成列表中。
	// None
	// TODO（bcmills）：让直接映射保持原样更有意义吗
	// 但是允许它引用不再在构建列表中的模块吗？
	// 这可能会使UpdateRoot复杂化，但在其他方面可能会更干净。
	direct := make(map[string]bool, len(rs.direct))
	for _, m := range roots {
		if rs.direct[m.Path] {
			direct[m.Path] = true
		}
	}
	return newRequirements(rs.depth, roots, direct), changed, nil
}

// limiterForEdit返回一个versionLimiter，其最大版本设置为
// mustSelect中每个模块路径的最大版本为列出的版本
// 其中，每个其他模块路径的最大版本就是最大版本
// 在rs的依赖关系图中找到的路径中，组合依赖关系
// mustSelect中版本的图表，或每个单独版本的依赖关系
// tryUpgrade中的模块版本。
func limiterForEdit(ctx context.Context, rs *Requirements, tryUpgrade, mustSelect []module.Version) (*versionLimiter, error) {
	mg, err := rs.Graph(ctx)
	if err != nil {
		return nil, err
	}

	maxVersion := map[string]string{} // 模块路径→ 版本
	restrictTo := func(m module.Version) {
		v, ok := maxVersion[m.Path]
		if !ok || cmpVersion(v, m.Version) > 0 {
			maxVersion[m.Path] = m.Version
		}
	}

	if rs.depth == eager {
		// Eager go.mod文件不指明哪些是可传递的依赖项
		// 实际上与主模块相关，所以我们必须假设任何模块
		// 它可以提供任何包，也就是说，任何模块
		// 版本不是“无”-可能相关。
		for _, m := range mg.BuildList() {
			restrictTo(m)
		}
	} else {
		// go.mod文件显式记录提供包的每个模块
		// 由主模块导入。
		// None
		// 如果我们需要降级在中找到的现有根或新根
		// tryUpgrade，我们不想让降级意外升级
		// 由主模块导入到任意版本的模块。
		// 然而，我们并不特别关心对模块的任意升级
		// （充其量）只提供通过测试导入的包
		// 主模块外部的依赖项。
		for _, m := range rs.rootModules {
			restrictTo(module.Version{
				Path:    m.Path,
				Version: mg.Selected(m.Path),
			})
		}
	}

	if err := raiseLimitsForUpgrades(ctx, maxVersion, rs.depth, tryUpgrade, mustSelect); err != nil {
		return nil, err
	}

	// mustSelect中的版本覆盖了我们天真地选择的任何内容-
	// 我们将根据需要降级其他模块，以满足它们的要求。
	for _, m := range mustSelect {
		restrictTo(m)
	}

	return newVersionLimiter(rs.depth, maxVersion), nil
}

// RaiseLimitsFrupGrades将maxVersions中的模块版本增加到
// 允许tryUpgrade中的每个模块所需的版本
// （单独或任意组合）和mustSelect中的所有模块
// （同时）作为根添加。
// None
// maxVersion中不存在的版本是不受限制的，并且假定
// 它们不会被提升为根需求（因此也不会做出贡献）
// 它们自己的依赖项（如果主模块是惰性的）。
// None
// 这些限制提供了模块升级的上限
// 偶然降级的一部分，如果需要降级以选择
// mustSelect中的版本。
func raiseLimitsForUpgrades(ctx context.Context, maxVersion map[string]string, depth modDepth, tryUpgrade []module.Version, mustSelect []module.Version) error {
	// allow将m.Path的限制至少提高到m.Version。
	// 如果m.Path已经不受限制，那么它仍然不受限制。
	allow := func(m module.Version) {
		v, ok := maxVersion[m.Path]
		if !ok {
			return // m、 路径不受限制。
		}
		if cmpVersion(v, m.Version) < 0 {
			maxVersion[m.Path] = m.Version
		}
	}

	var (
		eagerUpgrades  []module.Version
		isLazyRootPath map[string]bool
	)
	if depth == eager {
		eagerUpgrades = tryUpgrade
	} else {
		isLazyRootPath = make(map[string]bool, len(maxVersion))
		for p := range maxVersion {
			isLazyRootPath[p] = true
		}
		for _, m := range tryUpgrade {
			isLazyRootPath[m.Path] = true
		}
		for _, m := range mustSelect {
			isLazyRootPath[m.Path] = true
		}

		allowedRoot := map[module.Version]bool{}

		var allowRoot func(m module.Version) error
		allowRoot = func(m module.Version) error {
			if allowedRoot[m] {
				return nil
			}
			allowedRoot[m] = true

			if m.Path == Target.Path {
				// 目标已经被认为高于任何可能的m，因此我们
				// 无论如何都不会升级到它，扫描它也没有意义
				// 依赖关系。
				return nil
			}

			allow(m)

			summary, err := goModSummary(m)
			if err != nil {
				return err
			}
			if summary.depth == eager {
				// 为了提高效率，我们将把所有迫切需要的升级作为一个大文件加载
				// 图，而不是加载的（可能重叠）子图
				// 每次升级都是单独进行的。
				eagerUpgrades = append(eagerUpgrades, m)
				return nil
			}
			for _, r := range summary.require {
				if isLazyRootPath[r.Path] {
					// r可能会因为升级或降级而成为根目录，
					// 在这种情况下，它的依赖关系将不会被删除。
					// 我们也需要允许这些依赖项升级。
					if err := allowRoot(r); err != nil {
						return err
					}
				} else {
					// r不会成为根，所以它的依赖关系无关紧要。
					// 只允许r本身。
					allow(r)
				}
			}
			return nil
		}

		for _, m := range tryUpgrade {
			allowRoot(m)
		}
	}

	if len(eagerUpgrades) > 0 {
		// 计算所有急切升级的最大版本。
		// 由于这些模块都很急切，我们最终将扫描它们的所有
		// 可传递依赖项无论最终选择哪个版本，
		// 因为我们要扫描一个很大的依赖关系图，所以我们可能会得到
		// 不重新访问处于初始状态的依赖项的一个显著好处
		// 多个升级中的通用版本。
		upgradeGraph, err := readModGraph(ctx, eager, eagerUpgrades)
		if err != nil {
			if go117LazyTODO {
				// 计算从tryUpgrade中的模块路径到
				// 错误，以及从rs.rootModules到
				// tryUpgrade模块路径。返回一个*mvs.BuildListError，其中显示
				// 连接路径（中间有一个升级）。
			}
			return err
		}

		for _, r := range upgradeGraph.BuildList() {
			// 升级到m将升级到r，并且调用者请求我们
			// 尝试升级到m，这样就可以升级到r。
			allow(r)
		}
	}

	// 明确允许mustSelect暗示的任何（可传递的）升级。
	nextRoots := append([]module.Version(nil), mustSelect...)
	for nextRoots != nil {
		module.Sort(nextRoots)
		rs := newRequirements(depth, nextRoots, nil)
		nextRoots = nil

		rs, mustGraph, err := expandGraph(ctx, rs)
		if err != nil {
			return err
		}

		for _, r := range mustGraph.BuildList() {
			// mustSelect中的某些模块需要r，因此我们必须至少允许
			// r、 版本（除非它与mustSelect中的另一个条目冲突，在
			// 在这种情况下，无论哪种方式我们都会出错）。
			allow(r)

			if isLazyRootPath[r.Path] {
				if v, ok := rs.rootSelected(r.Path); ok && r.Version == v {
					// r已经是根，所以它的需求已经包含在
					// 生成列表。
					continue
				}

				// mustSelect中的依赖项可以升级（或降级）现有的
				// 根与r匹配，r将保留为根。然而，由于r不是
				// 作为rs的根，其依赖项已从该构建中删除
				// 列表我们需要显式地添加它，以便允许任何
				// r将引入的过渡升级。
				if nextRoots == nil {
					nextRoots = rs.rootModules // 已经封顶
				}
				nextRoots = append(nextRoots, r)
			}
		}
	}

	return nil
}

// 选择潜在导入的模块会增加所选版本的限制
// rs中可能提供导入包（直接或间接）的每个模块
// 间接）由主模块和tryUpgrade中的每个模块向
// rs或tryUpgrade中的最高版本，但不高于强制执行的最大值
// 通过限制器。
// None
// 它返回由限制器选择的模块版本列表，按
// 路径，以及一个布尔值，指示该列表是否与
// 从rs读取的模块列表。
func selectPotentiallyImportedModules(ctx context.Context, limiter *versionLimiter, rs *Requirements, tryUpgrade []module.Version) (mods []module.Version, changed bool, err error) {
	for _, m := range tryUpgrade {
		if err := limiter.UpgradeToward(ctx, m); err != nil {
			return nil, false, err
		}
	}

	var initial []module.Version
	if rs.depth == eager {
		mg, err := rs.Graph(ctx)
		if err != nil {
			return nil, false, err
		}
		initial = mg.BuildList()[1:]
	} else {
		initial = rs.rootModules
	}
	for _, m := range initial {
		if err := limiter.UpgradeToward(ctx, m); err != nil {
			return nil, false, err
		}
	}

	mods = make([]module.Version, 0, len(limiter.selected))
	for path, v := range limiter.selected {
		if v != "none" && path != Target.Path {
			mods = append(mods, module.Version{Path: path, Version: v})
		}
	}

	// 我们已经为每个模块确定了可接受的版本，但是
	// 版本之间不一定一致：一个升级版本或多个版本
	// 降级的模块可能需要更高（但仍然允许）版本的
	// 另一个较低版本可能需要不需要的无关依赖项
	// 实际上是相关的，所以我们需要计算实际选择的版本。
	mg, err := readModGraph(ctx, rs.depth, mods)
	if err != nil {
		return nil, false, err
	}
	mods = make([]module.Version, 0, len(limiter.selected))
	for path, _ := range limiter.selected {
		if path != Target.Path {
			if v := mg.Selected(path); v != "none" {
				mods = append(mods, module.Version{Path: path, Version: v})
			}
		}
	}
	module.Sort(mods)

	changed = !reflect.DeepEqual(mods, initial)

	return mods, changed, err
}

// versionLimiter跟踪可能为每个模块选择的版本
// 受可传递依赖项的最大版本的约束。
type versionLimiter struct {
	// 深度是模块的依赖项传递到的深度
	// 选择并向上升级将被加载。
	depth modDepth

	// max将每个模块路径映射到可为其选择的最大版本
	// 那条路。
	// None
	// 没有入口的路径是不受限制的，我们假设它们不会受到限制
	// 升级为根依赖项（因此，如果
	// 主模块是惰性的）。
	max map[string]string

	// “选定”将每个模块路径映射到其
	// 可传递依赖项不违反任何max版本。版本保持不变
	// 是在对给定对象调用UpgradeToward期间找到的最高值
	// 模块路径。
	// None
	// 如果在调用UpgradeToward for期间找到更高的可接受版本
	// 某些*其他*模块路径，不更新所选版本。
	// 忽略这些版本将为两个模块计算降级
	// 加在一起，接近将为每个
	// 隔离模块。（一个模块影响另一个模块的唯一方式是
	// 一个模块的最终降级版本明确要求更高的
	// 另一个版本。）
	// None
	// 每个模块的版本“无”始终不违反任何最大值
	// 版本，因此忽略版本“none”处的路径。
	selected map[string]string

	// dqReason记录每个遇到的版本是否为
	// 取消资格。
	dqReason map[module.Version]dqState

	// 要求将每个尚未取消资格的模块版本映射到
	// 这直接需要它。如果该版本被取消资格，则
	// 取消资格将传播到列表中的所有版本。
	requiring map[module.Version][]module.Version
}

// dqState表示模块版本是否以及为什么“不合格”
// 以符合其要求的方式使用。
// None
// 零dqState表示模块版本未知
// 被取消资格，或者因为它是正常的，或者因为我们目前正在穿越
// 包含它的循环。
type dqState struct {
	err      error          // 如果非零，则因无法读取模块要求而取消资格
	conflict module.Version // 取消资格，因为模块（传递）需要dep，这超过了其路径的最大版本约束
}

func (dq dqState) isDisqualified() bool {
	return dq != dqState{}
}

// newVersionLimiter返回限制模块路径的versionLimiter
// 在max中显示为关键点的。
// None
// max将每个模块路径映射到其最大版本；不存在的路径
// 在地图上是不受限制的。限制器假定不受限制的路径将
// 不能升级为根依赖项。
// None
// 如果深度是惰性的，那么如果传递给UpgradeToward或Select的模块是
// 它本身是惰性的，扫描时会跳过它的无限制依赖项
// 要求。
func newVersionLimiter(depth modDepth, max map[string]string) *versionLimiter {
	return &versionLimiter{
		depth:     depth,
		max:       max,
		selected:  map[string]string{Target.Path: Target.Version},
		dqReason:  map[module.Version]dqState{},
		requiring: map[module.Version][]module.Version{},
	}
}

// UpgradeTor尝试将所选m.Path版本升级到最接近的版本
// 可以在不违反l的最大版本限制的情况下转换为m.版本。
// None
// 如果depth是惰性的，而m本身是惰性的，那么
// 不遵循m的依赖关系。
func (l *versionLimiter) UpgradeToward(ctx context.Context, m module.Version) error {
	selected, ok := l.selected[m.Path]
	if ok {
		if cmpVersion(selected, m.Version) >= 0 {
			// 所选版本已至少为m，因此无需升级。
			return nil
		}
	} else {
		selected = "none"
	}

	if l.check(m, l.depth).isDisqualified() {
		candidates, err := versions(ctx, m.Path, CheckAllowed)
		if err != nil {
			// 这可能是到达存储库时出现的暂时性错误，
			// 而不是检索到的版本的永久错误。
			// None
			// TODO（golang.org/issue/31730，golang.org/issue/30134）：
			// 根据实际错误解码要执行的操作。
			return err
		}

		// 跳到<m.Version的候选项。
		i := sort.Search(len(candidates), func(i int) bool {
			return semver.Compare(candidates[i], m.Version) >= 0
		})
		candidates = candidates[:i]

		for l.check(m, l.depth).isDisqualified() {
			n := len(candidates)
			if n == 0 || cmpVersion(selected, candidates[n-1]) >= 0 {
				// 在已选择的版本之上，我们找不到合适的候选版本。
				// 保持该版本不变。
				return nil
			}
			m.Version, candidates = candidates[n-1], candidates[:n-1]
		}
	}

	l.selected[m.Path] = m.Version
	return nil
}

// Select尝试将所选m.Path版本设置为m.version。
func (l *versionLimiter) Select(m module.Version) (conflict module.Version, err error) {
	dq := l.check(m, l.depth)
	if !dq.isDisqualified() {
		l.selected[m.Path] = m.Version
	}
	return dq.conflict, dq.err
}

// 检查确定m（或其可传递依赖项）是否会违反l
// 最大版本限制（如果添加到模块需求图中）。
// None
// 如果深度是惰性的，而m本身是惰性的，那么
// 不遵循m的依赖关系。如果延迟加载不变量保持不变
// 对于目前为止的主模块，这些模块中的包位于
// 最好仅由从中加载的依赖项测试导入
// 外部模块。尽管我们希望保持“全方位测试”的可复制性
// 因为是可行的，我们不想保留那些仅仅是
// 充其量也只是勉强相关。
func (l *versionLimiter) check(m module.Version, depth modDepth) dqState {
	if m.Version == "none" || m == Target {
		// 版本“none”没有要求，目标的依赖项是
		// 同义反复的
		return dqState{}
	}

	if dq, seen := l.dqReason[m]; seen {
		return dq
	}
	l.dqReason[m] = dqState{}

	if max, ok := l.max[m.Path]; ok && cmpVersion(m.Version, max) > 0 {
		return l.disqualify(m, dqState{conflict: m})
	}

	summary, err := goModSummary(m)
	if err != nil {
		// 如果无法加载需求，则无法加载go.mod文件。
		// 发生这种情况的原因有很多，但通常
		// 表示模块的旧版本缺少或无效
		// go.mod文件。例如，如果example.com/mod之前发布了v2.0.0
		// 迁移到模块（v2.0.0+不兼容），然后添加有效的go.mod
		// 在v2.0.1中，从v2.0.1降级会导致此错误。
		// None
		// TODO（golang.org/issue/31730，golang.org/issue/30134）：如果
		// 是暂时的（我们无法下载go.mod），从
		// 降级。目前，我们无法判断这是什么样的错误。
		return l.disqualify(m, dqState{err: err})
	}

	if summary.depth == eager {
		depth = eager
	}
	for _, r := range summary.require {
		if depth == lazy {
			if _, restricted := l.max[r.Path]; !restricted {
				// r、 路径是不受限制的，所以我们不关心它是什么版本
				// 挑选出来的。我们假设r.Path不会成为根依赖项，所以
				// 因为m是惰性的，所以不会遵循r的依赖关系。
				continue
			}
		}

		if dq := l.check(r, depth); dq.isDisqualified() {
			return l.disqualify(m, dq)
		}

		// r及其依赖关系（可能暂时）是正常的。
		// None
		// 然而，如果需求图中有周期，我们可能只有
		// 到目前为止，检查了需求图的一部分，r（因此m）可能
		// 然而，我们会被一些我们还没有走过的道路所取消资格。记住这条边
		// 因此，如果出现这种情况，我们可以取消m及其依赖项的资格。
		l.requiring[r] = append(l.requiring[r], m)
	}

	return dqState{}
}

// 取消m（或其可传递依赖项之一）的记录资格
// 违反了l的最大版本限制。
func (l *versionLimiter) disqualify(m module.Version, dq dqState) dqState {
	if dq := l.dqReason[m]; dq.isDisqualified() {
		return dq
	}
	l.dqReason[m] = dq

	for _, p := range l.requiring[m] {
		l.disqualify(p, dqState{conflict: m})
	}
	// 现在我们已经取消了依赖于m的模块的资格，我们可以忘记了
	// 关于他们-我们不需要再次取消他们的资格。
	delete(l.requiring, m)
	return dq
}
